#include<stdio.h>
#include<stdlib.h>
int mergesort(int *a,int p,int r)
{
	if(p<r)
	{	
		int q;
		q=(p+r)/2;
		mergesort(a,p,q);
		mergesort(a,q+1,r);
		merge(a,p,q,r);
	}
}
int merge(int *a,int p,int q,int r)
{
	int i,j,k=0;
	i=p;
	j=q;
	int b[r-p+1];
	while(k<=r-p)
	{
		if((a[i]<=a[j+1]||j>=r)&&!(i>q))
		{
			b[k]=a[i];
			k++;
			i++;
		}
		else
		{
			b[k]=a[j+1];
			j++;
			k++;
		}
	}
	for(i=p;i<r+1;i++) a[i]=b[i-p];

	return 0;
}



int main()
{
	int i,j,k;
	int a[10]={2,4,1,6,5,7,3,8,9,2};
	mergesort(a,0,9);
	for(i=0;i<10;i++) printf("%d ",a[i]);
	return 0;
}
